#include<iostream>
#include<vector>
#include<string>
using namespace std;

template<class K>
struct HashFunc//当是浮点数、有符号的负数、指针，此时取模都能完美的解决
{
	size_t operator()(const K& key)
	{
		return (size_t)key;//强制转换
	}
};

//模板特化（要有原模版才能特化）
template<>
struct HashFunc<string>//当是字符串时，返回数字能解决，取模的问题
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;//降低ASCII相加后的重复率
			hash += e;//ASCII码相加
		}
		return hash;
	}
};

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& kv)
			:_data(data)
			,_next(nullptr)
		{}
	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;

		const HashTable<K, T, KeyOfT, Hash>* _pht;// 把Hash对象的指针传过来

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref operator*() { return _node->_data; }

		Ptr operator->() { return &_node->_data; }

		bool operator!=(const Self& s) { return _node != s._node; }

		Self& operator++()
		{
			if (_node->_next)
				_node = _node->_next;
			else// 桶为空
			{
				KeyOfT kot;
				hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
						break;
					++hashi;
				}

				if (hashi == _pht->_tables.size())
					_node = nullptr;
				else
					_node = _pht->_tables[hashi];
			}
			return *this;
		}

	};

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<T> Node;
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}
			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable() { _tables.resize(10, nullptr); }

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		//pair<Iterator, bool> Insert(const T& data)
		//{
		//	KeyOfT kot;
		//	Iterator it = Find(kot(data));
		//	if (it != End())
		//		return make_pair(it, false);
		//
		//	Hash hs;
		//	size_t hashi = hs(kot(data)) % _tables.size();
		//	if (_n == _tables.size())
		//	{
		//		vector<Node*> newtables(_tables.size() * 2, nullptr);
		//		for (size_t i = 0; i < _tables.size(); i++)
		//		{
		//			Node* cur = _tables[i];
		//			while (cur)
		//			{
		//				Node* next = cur->_next;
		//				size_t hashi = hs(cur->data) % newtables.size();
		//				cur->_next = newtables[hashi];
		//				newtables[hashi] = cur;
		//
		//				cur = next;
		//			}
		//			_tables[i] = nullptr;
		//		}
		//		_tables.swap(newtables);
		//	}
		//	// 头插
		//	Node* newnode = new Node(data);
		//	newnode->_next = _tables[hashi];
		//	_tables[hashi] = newnode;
		//	++_n;
		//	return make_pair(Iterator(newnode, this), true);
		//}

		pair<Iterator, bool> Insert(const T& data)
		{
			KeyOfT kot;
			Iterator it = Find(kot(data));
			//不允许重复
			if (it != End())
			{
				return make_pair(it, false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();//取模算出hashi对应的位置出来

			//控制负载因子
			//负载因子==1 扩容
			//负载因子越低，空间效率越低，时间效率越高
			//负载因子越高，空间效率越高，时间效率越低
			if (_n == _tables.size())//负载因子到1，进行扩容
			{
				//直接挪动结点
				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				{
					Node* cur = _tables[i];
					while (cur)//遍历桶
					{
						//提前保存下一个结点，不然下次找不到
						Node* next = cur->_next;

						//直接把旧表中的结点，挪到新表重新映射的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();//在新表找到对应的位置
						//头插到新表
						cur->_next = newtables[hashi];//我先指向桶的第一个
						newtables[hashi] = cur;//把桶的第一个给我

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//头插
			Node* newnode = new Node(data);
			//找到位置，进行头插
			newnode->_next = _tables[hashi];//（第一个的地址在表里面）表里面指向桶里的第一个
			_tables[hashi] = newnode;//把桶里面的第一个给newnode（在桶里面头插）
			++_n;

			return make_pair(Iterator(newnode, this), true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(key)) % _tables.size();//先算在表里面的位置
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//有这个结点，进行删除，分情况进行讨论
					if (prev == nullptr)
					{
						//没有前一个，直接指向下一个
						_tables[hashi] = cur->_next;
					}
					else
					{
						//有前一个，就让前一个的next指向我的后一个
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}


	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}